package Algorithm.backTracking;

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.List;

/**
 * 78. 子集 https://leetcode.cn/problems/subsets/
 * 题目简述：给你一个整数数组nums，数组中的元素互不相同。返回该数组所有可能的子集（幂集，包括空集）。
 */
public class Subsets {

    /**
     * 思路：回溯算法。关键点：每遍历到一个不同的路径都要将path加入结果集
     * 回溯递归函数参数：（结果集，已选择路径，下一步路径选择列表：数组nums中下标begin开头的子数组）
     * 回溯递归函数体：1.若begin==length，则数组已遍历完 直接return
     *              2.遍历当前选择列表[begin,length-1]：将选择加入路径，将path加入结果集，
     *              然后递归下一步选择列表，完毕后撤销上一步选择，继续遍历同层其他选择
     */
    public List<List<Integer>> subsets(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        result.add(new ArrayList<>());
        Deque<Integer> path = new ArrayDeque<>();
        backTracking(result, path, nums, 0);
        return result;
    }

    public void backTracking(List<List<Integer>> result, Deque<Integer> path, int[] nums, int begin) {
        if(begin == nums.length) return;
        //顺序性剪枝：剪去[0, begin)
        for(int i = begin;i < nums.length;i++) {
            path.add(nums[i]);
            result.add(new ArrayList<>(path));
            backTracking(result, path, nums, i+1);
            path.removeLast();
        }
    }
}
